\documentclass{beamer}
\usepackage[french]{babel}
\usepackage[latin1]{inputenc}
\usepackage{xcolor}
\usetheme{Singapore}
%\usetheme{progressbar}
\usepackage[eurosym]{eurofont}
%  \setbeamercolor{normal text}{fg=red,bg=blue}
\usepackage{multimedia}
\usepackage{listings}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{listings}

\newcommand{\super}[1]{\ensuremath{^{\textrm{#1}}}}
\newcommand{\sub}[1]{\ensuremath{_{\textrm{#1}}}}

\lstset{ %
language=C++,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
%framexrightmargin=3mm,
%numbers=right,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
stepnumber=2,                   % the step between two line-numbers. If it's 1 each line 
                                % will be numbered
numbersep=5pt,                  % how far the line-numbers are from the code
backgroundcolor=,  % choose the background color. You must add 
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,                   % adds a frame around the code
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
title=\lstname,                 % show the filename of files included with \lstinputlisting;
                                % also try caption instead of title
escapeinside={\%*}{*)},         % if you want to add a comment within your code
morekeywords={*,...}            % if you want to add more keywords to the set
}

%Nos de pages en bas a gauche
\addtobeamertemplate{footline}{\hfill\insertframenumber/\inserttotalframenumber\hspace{2em}\vspace{1em}\null}

% couleurs
\definecolor{Bblue}{rgb}{0.0,0.0,0.6}
\definecolor{Bred}{rgb}{0.5,0.0,0.0}
\definecolor{myblue}{rgb}{0.0,0.4,1} 

% cbold : passe du texte en couleur et en gras
\newcommand{\cbold}[2]{\textbf{\textcolor{#1}{#2}}}
% imp : met un texte en gras/bleu
\newcommand{\imp}[1]{\cbold{Bblue}{#1}}
% vimp : met un texte en gras/rouge
\newcommand{\vimp}[1]{\cbold{Bred}{#1}}
% iis : laisse un espace vertical simulant un double interligne
\newcommand{\iis}[0]{\vspace{5pt}}


\begin{document}

	\title{\textbf{Don't settle for eventual:\\ scalable causal consistency for wide-area storage with COPS}\\SOSP'11}
	\author{\textit{written by}\\ \textbf{Wyatt Lloyd et al.} \\\textit{presented by}\\ \textbf{Si-Mohamed Lamraoui\\  Ibrahim Safieddine}} 
	\institute[UJF]{UFR IM$^{2}$AG}
	\logo{\includegraphics[width=1cm]{images/ujf_neu.jpg}}
	\date{\tiny version 1.0} 
	
	\setbeamertemplate{navigation symbols}{}
	\setcounter{tocdepth}{1}
	
	
	% ======================================================
	{
	%\setbeamertemplate{footline}[default]
	\begin{frame}
	\titlepage
	\end{frame}
	
	
	% ======================================================
	\logo{\includegraphics[width=1cm]{images/ujf_neu.jpg}}
	%\begin{frame}
	%\frametitle{Plan}
	%\tableofcontents
	%\end{frame}
	}
	\logo{\includegraphics[width=1cm]{images/ujf_neu.jpg}}
	\addtocounter{framenumber}{-1}


	
		
	\section{Introduction}
	% ======================================================
	\begin{frame}{}
	\begin{center}
	\begin{Large} \imp{Introduction} \end{Large}
	\end{center}
	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{Goal of COPS}
		
		\center \textbf{Modern Web Services}

		\begin{columns} \begin{column}[1]{4cm}
		\center \includegraphics[width=130px]{images/map.pdf}
		\end{column} \begin{column}[1]{5cm}
		\begin{itemize}
		\item Availability
		\item Partition tolerance
		\item \vimp{Bad consistency}
		\end{itemize}
		\end{column} \end{columns}

		\bigskip\bigskip

	\end{frame}
	
	% -------------------------------------------------------------------
	\begin{frame}{Goal of COPS}

		\center \textbf{Modern Web Services}

		\begin{columns} \begin{column}[1]{4cm}
		\center \includegraphics[width=130px]{images/map.pdf}
		\end{column} \begin{column}[1]{5cm}
		\begin{itemize}
		\item Availability
		\item Partition tolerance
		\item \vimp{Bad consistency}
		\end{itemize}
		\end{column} \end{columns}
	
		\center \textbf{ALPS systems : }\\ 
		\textbf{A}vailability, low \textbf{L}atency, \textbf{P}artition-tolerance, high \textbf{S}calability 


	\end{frame}
	
   	% -------------------------------------------------------------------
	\begin{frame}{Goal of COPS}

	\begin{block}{The CAP Theorem}
	\textit{It is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:\\
	- Consistency\\ %(all nodes see the same data at the same time)
	- Availability\\ %(a guarantee that every request receives a response about whether it was successful or failed)
	- Partition tolerance %(the system continues to operate despite arbitrary message loss)
	}
	\end{block}
	\bigskip\bigskip\bigskip\bigskip\bigskip

	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{Goal of COPS}

	\begin{block}{The CAP Theorem}
	\textit{It is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:\\
	- Consistency\\ %(all nodes see the same data at the same time)
	- Availability\\ %(a guarantee that every request receives a response about whether it was successful or failed)
	- Partition tolerance %(the system continues to operate despite arbitrary message loss)
	}
	\end{block}

	\bigskip\bigskip

	\textbf{$\Rightarrow$ COPS: \\Seek strongest consistency model that is achievable under these constraints.} 

	\end{frame}



	% -------------------------------------------------------------------
	\begin{frame}{Goal of COPS}

	\center \textbf{COPS's causal+ consistency}\\

	\begin{itemize}
	\item Properties :
		\begin{itemize}
		\item[-] Causal consistency
		\item[-] Convergent conflict handling
		\end{itemize}
	\item Pros :
		\begin{itemize}
		\item[-] Makes systems easier for programmers
		\item[-] Better user experience
		\end{itemize}
	\end{itemize}
	\bigskip
	\center \includegraphics[width=230px]{images/causal.pdf}


	\end{frame}


	% -------------------------------------------------------------------
	\begin{frame}{Related Work}

	\begin{itemize}
	\item ALPS Systems
		\begin{itemize}
		\item[-] Amazon's Dynamo
		\item[-] LinkedIn's projet Voldemort
		\end{itemize}
	\item Causally Consistent Systems
		\begin{itemize}
		\item[-] Bayou (SQL-Like interface)
		\item[-] TACT
		\end{itemize}
	\item Linearizable Systems
		\begin{itemize}
		\item[-] CAP
		\item[-] CRAQ
		\end{itemize}
	\item Transactions
		\begin{itemize}
		\item[-] R* Databases
		\item[-] Walter
		\end{itemize}
	\end{itemize}

	\end{frame}
	



	\section{Design of COPS/COPS-GT}
	% ======================================================
	\begin{frame}{}
	\begin{center}
	\begin{Large} \imp{Design of COPS/COPS-GT} \end{Large}
	\end{center}
	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{Clusters of Order-Preserving Servers (COPS)}
		
	\textbf{What is COPS ?}\\
	\begin{itemize}
	\item Distributed storage system
	\item Causal+ consistency
	\item APLS properties
	\end{itemize}
	\bigskip
	\textbf{Two distinct versions:}\\
	\begin{itemize}
	\item COPS : causal+ consistent data store
	\item COPS-GT : COPS \& \textit{get transactions}
	\end{itemize}

	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{Clusters of Order-Preserving Servers (COPS)}
		
	 \center \includegraphics[width=250px]{images/cops1.pdf}

	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{Clusters of Order-Preserving Servers (COPS)}

	 \center \includegraphics[width=250px]{images/cops2.pdf}		

	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{Clusters of Order-Preserving Servers (COPS)}

	 \center \includegraphics[width=250px]{images/cops3.pdf}		

	\end{frame}

	%-------------------------------------------------------------------
	\begin{frame}{Clusters of Order-Preserving Servers (COPS)}

	 \center \includegraphics[width=250px]{images/cops4.pdf}		

	\end{frame}

	%-------------------------------------------------------------------
	\begin{frame}{Clusters of Order-Preserving Servers (COPS)}

	 \center \includegraphics[width=250px]{images/cops5.pdf}		

	\end{frame}

	%-------------------------------------------------------------------
	\begin{frame}{Clusters of Order-Preserving Servers (COPS)}

		\center \textbf{Main Sofware Components }\\
		\bigskip
		\begin{columns} \begin{column}[1]{4cm}
		\center Key-value store
		\center \includegraphics[width=80px]{images/node.pdf}
		\end{column} \begin{column}[1]{5cm}
		\center \includegraphics[width=80px]{images/lib.pdf}
		\center Client library
		\end{column} \end{columns}

	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{The COPS Key-Value Store}
	
	\center \includegraphics[width=200px]{images/key1.pdf}

	\end{frame}

	%-------------------------------------------------------------------
	\begin{frame}{The COPS Key-Value Store}
	
	\center \textbf{Key Ranges}
	\center \includegraphics[width=200px]{images/key2.pdf}

	\end{frame}

	%-------------------------------------------------------------------
	\begin{frame}{The COPS Key-Value Store}
	
	\center \textbf{Relication}
	\center \includegraphics[width=200px]{images/key3.pdf}
	\center Send to equivalent nodes

	\end{frame}

	%-------------------------------------------------------------------
	\begin{frame}{The COPS Key-Value Store}
	
	\center \textbf{Replication Checking Mecanism}
	\center \includegraphics[width=150px]{images/key4-1.pdf}\\
	\begin{itemize}
	\item[ $\Rightarrow$] [write] causal consistency order
 	\item[ $\Rightarrow$] [read] never block
	\end{itemize}

	\end{frame}

	%-------------------------------------------------------------------
	\begin{frame}{The COPS Key-Value Store}
	
	\center \textbf{Replication Checking Mecanism}
	\center \includegraphics[width=150px]{images/key4-2.pdf}\\
	\begin{itemize}
	\item[ $\Rightarrow$] [write] causal consistency order
 	\item[ $\Rightarrow$] [read] never block
	\end{itemize}

	\end{frame}

	%-------------------------------------------------------------------
	\begin{frame}{The COPS Key-Value Store}
	
	\center \textbf{Relication Checking Mecanism}
	\center \includegraphics[width=150px]{images/key4-3.pdf}\\
	\begin{itemize}
	\item[ $\Rightarrow$] [write] causal consistency order
 	\item[ $\Rightarrow$] [read] never block
	\end{itemize}

	\end{frame}
	
   	% -------------------------------------------------------------------
	\begin{frame}{Client Library and Interface}
		
		\center \textbf{Simple Programming Interface}
		\center \includegraphics[width=300px]{images/client.pdf}

	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{Client Library and Interface}
		
		\center \includegraphics[width=200px]{images/dep.pdf}
		\bigskip
		\begin{itemize}
		\item COPS :
			\begin{itemize}
			\item[-] nearest dependencies
			\end{itemize}
		\item COPS-GT :
			\begin{itemize}
			\item[-] all dependencies
			\end{itemize}
		\end{itemize}

	\end{frame}

   	% -------------------------------------------------------------------
	\begin{frame}{Writing/Reading Values in COPS/COPS-GT}
		
		\center \includegraphics[width=300px]{images/reading1.pdf}
		\bigskip
		\begin{itemize}
		\item get \(( key, ctx\_id\))
		\end{itemize}

	\end{frame}


	   	
	% -------------------------------------------------------------------
	\begin{frame}{Writing/Reading Values in COPS/COPS-GT}
		
		\center \includegraphics[width=300px]{images/reading2.pdf}
		\bigskip
		\begin{itemize}
		\item get \(( key, ctx\_id\))
		\end{itemize}

	\end{frame}

	   	
	% -------------------------------------------------------------------
	\begin{frame}{Writing/Reading Values in COPS/COPS-GT}
		
		\center \includegraphics[width=300px]{images/reading3.pdf}
		\bigskip
		\begin{itemize}
		\item get\_by\_version \(( key, version\))
		\end{itemize}

	\end{frame}

	   	
	% -------------------------------------------------------------------
	\begin{frame}{Writing/Reading Values in COPS/COPS-GT}
		
		\center \includegraphics[width=300px]{images/writing1.pdf}
		\bigskip
		\begin{itemize}
		\item put \(( key, value, ctx\_id\))
		\end{itemize}

	\end{frame}


	% -------------------------------------------------------------------
	\begin{frame}{Writing/Reading Values in COPS/COPS-GT}
		
		\center \includegraphics[width=300px]{images/writing2.pdf}
		\bigskip
		\begin{itemize}
		\item put\_after \(( key, value, [deps], nearest, version\))
		\end{itemize}

	\end{frame}


	% -------------------------------------------------------------------
	\begin{frame}{Writing/Reading Values in COPS/COPS-GT}
		
		\center \includegraphics[width=300px]{images/writing3.pdf}
		\bigskip
		\begin{itemize}
		\item put\_after \(( key, value, [deps], nearest, version\))
		\end{itemize}

	\end{frame}


	% -------------------------------------------------------------------
	\begin{frame}{Writing/Reading Values in COPS/COPS-GT}
		
		\center \includegraphics[width=240px]{images/writing4.pdf}
		\bigskip
		\begin{itemize}
		\item dep\_check \(( key, version\))
		\end{itemize}

	\end{frame}



   	% -------------------------------------------------------------------
	\begin{frame}{Get Transaction in COPS-GT}
		
		\center \includegraphics[width=200px]{images/transaction1.pdf}

	\end{frame}


	% -------------------------------------------------------------------
	\begin{frame}{Get Transaction in COPS-GT}	
		\center \includegraphics[width=200px]{images/transaction2.pdf}

	\end{frame}


	% -------------------------------------------------------------------
	\begin{frame}{Get Transaction in COPS-GT}	
		\center \includegraphics[width=200px]{images/transaction3.pdf}

	\end{frame}


	% -------------------------------------------------------------------
	\begin{frame}{Get Transaction in COPS-GT}	
		\center \includegraphics[width=200px]{images/transaction4.pdf}
		\bigskip
		\begin{itemize}
		\item To retreive multiple values in a causal+ consistent manner, a client calls get\_trans with the desired set of keys.
		\end{itemize}

	\end{frame}




	\section{Evaluation}
	% ======================================================
	\begin{frame}{}
	\begin{center}
	\begin{Large} \imp{Evaluation} \end{Large}
	\end{center}
	\end{frame}
	

	 % -------------------------------------------------------------------
	\begin{frame}{Evaluation}
		
		\begin{itemize}
		\item 13,000 lines of C++ code
		\item 70 servers
			\begin{itemize}
			\item[-] 2x6 core Intel Xeon X5650 CPU
			\item[-] 48 GB RAM
			\item[-] 3x1TB HDD
			\item[-] 2x1GigE network ports
			\end{itemize}
		\end{itemize}


	\end{frame}

	
   	% -------------------------------------------------------------------
	\begin{frame}{Scalability}
		
	\includegraphics[width=300px]{images/eval-scala.pdf}


	\end{frame}







	\section{Conclusion}
	% ======================================================
	\begin{frame}{}
	\begin{center}
	\begin{Large} \imp{Conlusion} \end{Large}


	\end{center}
	\end{frame}

	% -------------------------------------------------------------------
	\begin{frame}{Conclusion}


		\begin{itemize}
		\item COPS respects the ALPS and casual+ consistency
		\item COPS-GT uses transactions to ensure causal+ consistency and guarantee low latency
		\end{itemize}



	\end{frame}


	% -------------------------------------------------------------------
	\begin{frame}

		\begin{center}
			\includegraphics[height=100px]{images/end.pdf}
			\begin{LARGE}
			\textbf{\\Thank you\\Questions ?}
			\end{LARGE}
		\end{center}
	\end{frame}





\end{document}
